package com.salim.leetcode.$16;

import java.util.Arrays;

public class ThreeSumClosest {
    public int threeSumClosest(int[] nums, int target) {
        if(nums.length<3){
            return 0;
        }
        Arrays.sort(nums);
        int sum = nums[0]+nums[1]+nums[2];

        for(int x=0;x<nums.length-2;x++){
            if(x==0 ||nums[x] != nums[x-1]){
                int base = nums[x];
                int left = x+1;
                int right = nums.length-1;
                while (left<right){
                    if(Math.abs(nums[left]+nums[right]+base-target)<Math.abs(sum - target)){
                        sum = nums[left]+nums[right]+base;
                        while (left<right && nums[left]==nums[left+1]){
                            left+=1;
                        }
                        while (right>left && nums[right-1]==nums[right]){
                            right-=1;
                        }
                    }
                    if(sum==target){
                        return sum;
                    }
                    if(nums[left]+nums[right]>target-base){
                        right-=1;
                    }else{
                        left+=1;
                    }
                }
            }
        }

        return sum;
    }


    public static void main(String[] args){
        ThreeSumClosest threeSum = new ThreeSumClosest();
        System.out.println(threeSum.threeSumClosest(new int[]{-1, 2, 1, -4},1));
        ThreeSumClosest threeSum1 = new ThreeSumClosest();
        System.out.println(threeSum1.threeSumClosest(new int[]{0, 1, 2},0));
        ThreeSumClosest threeSum2 = new ThreeSumClosest();
        System.out.println(threeSum2.threeSumClosest(new int[]{0, 2, 1,-3},0));
        ThreeSumClosest threeSum3 = new ThreeSumClosest();
        System.out.println(threeSum3.threeSumClosest(new int[]{0,2,1,-3},1));
    }
}
